1. Field of the Invention
The present invention concerns a method for equalizing symbols received from a transmission channel and decoding data therefrom. The invention more specifically concerns an equalization method which is implemented in a digital signal processor (DSP).
2. Description of the Related Art
Equalization is a well known method for removing Inter Symbol Interference (ISI) affecting a transmission channel.
The signal samples at the channel output can be expressed as:                               R          k                =                                            ∑                              i                =                0                                            L                -                1                                      ⁢                                          c                i                            ⁢                              D                                  k                  -                  i                                                              +                      η            k                                              (        1        )            
where ci are the channel coefficients defining the impulse response of the transmission channel (CIR), L is the delay spread of the channel, Dk-i is a M-ary modulated symbol and xcex7k is the sampled additive white Gaussian (AWG) noise affecting the channel. From equation (1) the transmission channel can be viewed as a finite impulse response filter with L taps.
A first class of equalization methods is concerned with symbol-by-symbol equalization. A simple equalization method consists in using a transverse linear filter for cancelling the ISI symbol by symbol. Of course, the tap coefficients of the transversal filter can be adapted to track the variations of the channel characteristics. However linear equalization performs poorly due to the effect of noise enhancement. This effect is mitigated in nonlinear Decision Feedback Equalization (DFE). A decision feedback equalizer comprises two parts: a feedforward part identical to a transverse linear filter and a feedback part including a decision step on the received symbol. The feedback part estimates the ISI contributed by the previously decided symbols and subtracts this estimation from the transverse linear filter output before the decision on the current symbol is made.
A second class of equalization methods derives from a Maximum Likelihood Sequence approach called therefore Maximum Likelihood Sequence Estimation (NILSE). According to this approach, the discrete memory channel is modelled as a finite-state machine, the internal register of which having the length of the channel memory. The most likely transmitted sequence Dk, knowing the received sequence Rk and the channel coefficients, is obtained by the Viterbi algorithm. Since the number of states of the trellis involved in the Viterbi algorithm grows exponentially with the channel memory length, several proposals have been made to reduce the number of states to be taken into account. In a first attempt to mitigate this effect, DDFSE (Delayed Decision Feedback Sequence Estimation) combines MLSE and DYE techniques by truncating the channel memory to a reduced number of terms and by removing in the branch metrics the tail of the ISI using a decision made on the surviving sequence at an earlier step (tentative decision). A further improvement with respect to error propagation, called RSSE, (Reduced State Sequence Estimation) was inspired by an Ungerboeck-like set partitioning principle. The RSSE algorithm was originally disclosed in the article of V. M. Eyuboglu et al. entitled xe2x80x9cReduce-state sequence estimation with set partitioning and decision feedbackxe2x80x9d, published in IEEE Trans. Commun., Vol. 36, pages 13-20, January 1988. Broadly speaking, in RSSE the symbols are partitioned into subsets and Viterbi decoding is performed on a subset-trellis, a node or subset-state of the subset-trellis being a vector of subset labels instead of a vector of symbols like in DDFSE. An advantage of RSSE over DDFSE is that it does not use tentative decisions but embeds the uncertainty of the channel response within the trellis structure.
Another possible way of relaxing the constraints in the decoding trellis is the list-type generalization of the Viterbi algorithm (GVA) proposed by T. Hashimoto in the article entitled xe2x80x9cA list-type reduced-constraint generalization of the Viterbi algorithmxe2x80x9d published in IEEE Trans. Inform. Theory, vol. IT-33, No6, Nov. 1987, pages 866-876. The Viterbi algorithm is generalized in that, for a given state in the trellis diagram, a predetermined. number S of paths (survivors) leading to that state, (instead of a single one in the conventional Viterbi algorithm) are retained for the next step. The retained paths are then extended by one branch corresponding to the assumed received symbol and the extended paths are submitted to a selection procedure leaving again S survivors per state. The GVA was applied to equalisation by Hashimoto himself in the above mentioned paper and a list-type Viterbi equalizer and later developed by Kubo et al. the article entitled xe2x80x9cA List-output Viterbi equalizer with two kinds of metric criteriaxe2x80x9d published in Proc. IEEE International Conference on Universal Personnal Comm. ""98, pages 1209-1213.
Both RSSE and LOVE (List Output Viterbi Equalization) can be regarded as particular cases of Per Survivor Processing (PSP) described in the article of R. Raheli et al. entitled xe2x80x9cPer Survivor Processingxe2x80x9d and published in Digital Signal Processing, No3, July 1993, pages 175-187. PSP generally allows joint channel estimation and equalization by incorporating in the Viterbi algorithm a data aided estimation of the channel coefficients. This technique is particularly useful in mobile telecommunication for equalization of fast fading channels.
Recently, a new method of equalisation has been derived from the seminal principle of turbo-decoding discovered by C. Berrou, A. Glavieux, P. Thitimajshima, and set out in the article entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding: Turbo-codingxe2x80x9d, ICC ""93, Vol. 2/3, May 1993, pages 1064-1071. This principle has been successfully applied to equalization by C. Douillard et al. as described in the article entitled xe2x80x9cIterative correction of Intersymbol Interference: Turbo-equalizationxe2x80x9d published in European Trans. Telecomm., Vol. 6, No5, Sept./Oct. 95, pages 507-511.
The basic principle underlying turbo-equalization is that an ISI channel can be regarded as a convolutional coder and therefore the concatenation of a coder, an interleaver and the transmission channel itself can be considered as a turbo-coder.
Turbo-equalization is based on an iterative joint equalization and channel decoding process. FIG. 1 shows an example of a transmission system using turbo-equalization. The transmitter comprises a systematic coder (100), e.g. a systematic convolutional coder (K,R) where K is constraint length and R is the binary rate, which encodes the input data Ik into error-control coded data Yn, an interleaver (110) outputting interleaved data Ynxe2x80x2, and a M-ary modulator (120), e.g. a BPSK modulator or a QAM modulator. At the receiver side, the turbo-equalizer TE is represented with dotted lines. The symbols Rnxe2x80x2affected by ISI are supplied to a soft equalizer (140) which outputs soft values An, representing the reliability of the estimation of Ynxe2x80x2. The soft equalization may be implemented by a Soft Output Viterbi Algorithm (SOYA) as described in the article of J. Hagenauer and P. Hoeher entitled xe2x80x9cA Viterbi algorithm with soft-decision outputs and its applicationsxe2x80x9d published in Proc. IEEE Globecorn ""89, pages 47.1.1-47.1.7. Alternately the Maximum A Posteriori (MAP) algorithm initially described in the article of L. Bahl, J. Cocke, F. Jelinek and J. Raviv published in IEEE on Information Theory, vol. IT-20, March 1974, pages 284-287 or a variant thereof (e.g. Log MAP, Max Log MAP) can be used. The latter algorithms will be generically referred to in the following as APP-type algorithms since they all provide the a posteriori probability for each bit to be decided. For example, the soft-equalizer of FIG. 1 implements the Log MAP algorithm which conveniently expresses the reliability information in the form of a Log Likelihood ratio xcex9nxe2x80x2,=xcex9(Ynxe2x80x2,). The soft values An are then de-interleaved by the de-interleaver (150) and supplied to a soft-output decoder which may be again a SOYA decoder or an APP-type decoder. The soft decoder uses these soft values and the knowledge of the coding algorithm to form soft estimates xcex9k=xcex9(Ik) of the initial data Ik which in turn permit to refine the estimation of the received symbols. For that, the latter estimates are passed back to the equalization stage. More precisely, the extrinsic information Extk produced by the decoding stage, i.e. the contribution of that stage to the reliability of the estimation, is obtained by subtracting in (191) the soft-output from the soft-input of the decoder. The extrinsic information Extk is then interleaved in interleaver (180) and fed back as a priori information to the soft equalizer (140). The extrinsic information derived from a stage must not be included in the soft input of the same stage. Hence, the extrinsic information Extk is subtracted in (191) from the output of the soft equalizer. The iteration process repeats until the estimation converges or until a time limit is reached. The soft output of the decoder is then compared to a threshold (170) to provide a hard output, i.e. a decision Ik on the bit value.
The reduced state technique has been successfully transposed to the MAP algorithm with the view of applying it to turbo-equalization. In particular, a List-type MAP equalizer has been described in unpublished French patent applications FR-A 0000207 and FR-A-0002066 filed by the Applicant on 4.1.2000 and 15.2.2000 respectively and included herein by reference.
The idea of joint channel estimation and equalization has also pervaded turbo-equalization. L. Davis, I. Collings and P. Hoeher have proposed in an article entitled xe2x80x9cJoint MAP equalization and channel estimation for frequency-selective fast fading channelsxe2x80x9d published in Proc. IEEE Globecom ""98, pages 53-58 a turboequalizer comprising a MAP equalizer making use of an expanded state trellis. The expansion of the state trellis beyond the channel memory length introduces additional degrees of freedom which are used for estimating the channel parameters. This method is more particularly useful for channels exhibiting fast varying characteristics for example in case of a transmission channel with a high velocity mobile terminal.
Another possible structure of turboequalizer is described in the article of A. Glavieux et al. entitled xe2x80x9cTurbo-equalization over a frequency selective channelxe2x80x9d, International Symposium on Turbo-codesxe2x80x9d, Brest, Sept. 97. In place of the MAP equalizer illustrated in FIG. 1, the first stage of the turboequalizer comprises a transversal linear filter for cancelling ISI from the received symbols in a decision directed mode followed by a M-ary to binary soft decoder.
Although the overall equalization process may be carried out by a plurality of dedicated processing units, a single digital signal processor (DSP) is preferred in practice. In such instance, the DSP carries out the various steps of equalization per se, deinterleaving, channel and, possibly, source decoding. However, since the processing capacity of the DSP is limited, the processing time may exceed the maximum delay normally accepted for a telephone transmission. Of course, the choice of a DSP of higher capacity entails additional costs.
A subsidiary problem arises when the propagation conditions over the transmission channel vary. It is known from the state of the art to adapt the parameters of the equalizer (e.g. adaptive filter with variable number of taps) or to modify the decoder (in concert with the encoder) e.g. by changing the puncturing rate in a channel encoder/decoder or changing the compression algorithm in a source encoder/decoder. This change may cause a temporary overrun of the processing capacity of the DSP. On the other hand, the choice of an oversized DSP which complies with the xe2x80x9cworst-casexe2x80x9d requirements is economically expensive and technically unsatisfactory.
The object of the present invention is to propose a method (and a corresponding device) for equalizing symbols received from a transmission channel and decoding data therefrom which solves the above addressed problems.
The method for equalizing symbols received from a transmission channel and for decoding data therefrom includes a sequence of processing steps Ei using an available resource R. Each processing step Ei involves a resource cost Ri (Tij) depending upon parameters Tij relative to an algorithm carried out by said processing step Ei. The method is characterized in that at least a subset of the parameters Tij is controlled so as to maximize a criterion of performance under the constraint:             ∑      i        ⁢                  R        i            ⁡              (                  T          ij                )              ≤      R    .  